/**
 * ReversePair.java created by zhangzhidong 
 * at 下午7:36:30 2016年10月9日
 */
package algorithm;
public class ReversePair {
	   public int InversePairs(int [] array) {
	        return get(array,0,array.length-1);
	    }
	    public int get(int []arr,int start,int end){
	        if(start>=end) return 0;
			int mid = (start+end)/2;
	        int l = get(arr,start,mid);
	        int r = get(arr,mid+1,end);
	    	return l+r+cross(arr,start,mid+1,end);
	    }
	    public int cross(int arr[],int start,int mid,int end){
			int num = 0;
	        int temp [] = new int[end-start+1];
	        int ls = start;
	        int rs = mid;
	        int index = 0;
	        while(ls<mid && rs<=end){
	            if(arr[ls]<arr[rs]){
					temp[index++]=arr[ls];
	                ls++;
	            }else{
	            	//arr[ls]>arr[rs]
	                num+=(rs-mid+1);
	                temp[index++] = arr[rs];
	                rs++;
	            }
	        }
	        while(ls<mid){
	        	temp[index++] = arr[ls];
	            //num+=(ls-start+1);
	            ls++;
	        }
	        while(rs<=end){
	            temp[index++] = arr[rs];
	            rs++;
	        }
	        index=0;
	        for(int i=start;i<=end;i++){
	        	arr[i] = temp[index++];
	        }
	        return num;
	    
	    }
	    public static void main(String args[]){
	    	int arr[] = new int[]{364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
	    	System.out.println(new ReversePair().InversePairs(arr));
	    }
}
